package graph;

import java.util.Scanner;

/**
 * 卡108.冗余连接
 * 题目描述
 * 有一个图，它是一棵树，他是拥有 n 个节点（节点编号1到n）和 n - 1 条边的连通无环无向图（其实就是一个线形图），如图：
 *
 * 现在在这棵树上的基础上，添加一条边（依然是n个节点，但有n条边），使这个图变成了有环图，如图：
 *
 * 先请你找出冗余边，删除后，使该图可以重新变成一棵树。
 * 输入描述
 * 第一行包含一个整数 N，表示图的节点个数和边的个数。
 * 后续 N 行，每行包含两个整数 s 和 t，表示图中 s 和 t 之间有一条边。
 * 输出描述
 * 输出一条可以删除的边。如果有多个答案，请删除标准输入中最后出现的那条边。
 */

/**
 * 一刷二刷思路一样
 */
public class redundantconnection {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        DisJoint disJoint = new DisJoint(n + 1);
        for (int i = 0; i < n; i++) {
            int s = sc.nextInt();
            int t = sc.nextInt();
            if (!disJoint.isSame(s, t)) {
                disJoint.join(s, t);
            } else {
                System.out.println(s + " " + t);
            }
        }
    }
}
